package binary_tree

func GetHeadSubBst(root *Node) *Node {
	if root == nil {return root}
	n := GetMaxSubBstSize(root)
	if n != 0 {
		return root
	}
	leftAns := GetHeadSubBst(root.Left)
	rightAns := GetHeadSubBst(root.Right)
	if GetMaxSubBstSize(leftAns) > GetMaxSubBstSize(rightAns) {
		return leftAns
	}
	return rightAns
}

func GetHeadSubBst2(root *Node) *Node {
	if root == nil {return root}
	return HeadSubBstProcess(root).BstHead
}

type HeadSubBstInfo struct {
	BstHead *Node
	min     int
	max     int
	size    int
}

func HeadSubBstProcess(node *Node) *HeadSubBstInfo {
	if node == nil {
		return nil
	}
	leftInfo := HeadSubBstProcess(node.Left)
	rightInfo := HeadSubBstProcess(node.Right)

	minV, maxV := node.Val, node.Val
	if leftInfo != nil {
		minV = min(leftInfo.min, minV)
		maxV = max(leftInfo.max, maxV)
	}
	if rightInfo != nil {
		minV = min(rightInfo.min, minV)
		maxV = max(rightInfo.max, maxV)
	}

	isBst := true
	if leftInfo != nil && rightInfo != nil {
		isBst = node.Left == leftInfo.BstHead && node.Right == rightInfo.BstHead && node.Val > leftInfo.max && node.Val < rightInfo.min
	} else if leftInfo == nil && rightInfo != nil {
		isBst = node.Right == rightInfo.BstHead && node.Val < rightInfo.min
	} else if leftInfo != nil && rightInfo == nil {
		isBst = node.Left == leftInfo.BstHead && node.Val > leftInfo.max
	}

	var curBstHead *Node
	var curSize int
	if isBst {
		curBstHead = node
		if leftInfo != nil && rightInfo != nil {
			curSize = leftInfo.size + rightInfo.size + 1
		} else if leftInfo == nil && rightInfo != nil {
			curSize = rightInfo.size + 1
		} else if leftInfo != nil && rightInfo == nil{
			curSize = leftInfo.size + 1
		} else {
			curSize = 1
		}
	} else {
		if leftInfo != nil && rightInfo != nil {
			if leftInfo.size > rightInfo.size {
				curBstHead = leftInfo.BstHead
				curSize = leftInfo.size
			} else {
				curBstHead = rightInfo.BstHead
				curSize = rightInfo.size
			}
		} else if leftInfo != nil && rightInfo == nil {
			curBstHead = leftInfo.BstHead
			curSize = leftInfo.size
		} else if leftInfo == nil && rightInfo != nil {
			curBstHead = rightInfo.BstHead
			curSize = rightInfo.size
		}
	}
	return &HeadSubBstInfo{curBstHead, minV, maxV, curSize}
}